package NewCoder;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;

class Interval {
      int start;
      int end;
      Interval() { start = 0; end = 0; }
      Interval(int s, int e) { start = s; end = e; }
  }
public class BM89 {
    public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
        ArrayList<Interval> list=new ArrayList<>();
        if(intervals.size()==0) return list;
        //重载比较，按照区间首排序
        Collections.sort(intervals,new Comparator<Interval>(){
            public int compare(Interval o1,Interval o2){
                if(o1.start!=o2.start){
                    return o1.start-o2.start;
                }else{
                    return o1.end-o2.end;
                }
            }
        });
        list.add(intervals.get(0));
        int count=0;
        for(int i=1;i<intervals.size();i++){
            Interval o1=intervals.get(i);
            Interval o2=list.get(count);
            if(o2.end<o1.start){
                list.add(o1);
                count++;
            }else{
                list.remove(count);
                Interval s=new Interval(o2.start,o1.end);
                if(o1.end<o2.end){
                    s.end=o2.end;
                }
                list.add(s);
            }
        }
        return list;
    }
}
